/*******************************************************************************
* FileName:         BinTree.h
* Author:           李智铭
* Student Number:   3022206093
* Date:             2024/11/20 17:00:00
* Version:          v1.0
* Description:      Data Structure Experiment #8
*******************************************************************************/
#include <vector>
#ifndef BinTree_H
#define BinTree_H

class BinTree{
private:
    struct node{
        int val;
        int id;   //节点编号
        node* left;
        node* right;
        bool isThreadLeft; // 左标志位，true 表示指向前驱
        bool isThreadRight; // 右标志位，true 表示指向后继
    };
    node* root;
    int depth;
    int count;
    int current_id;   //新节点预编号
public:
    /**
     *  构造函数，初始化二叉排序树
        @name BinTree();
        @param
        @return 
    */
    BinTree();

    /**
     *  析构函数，销毁二叉排序树
        @name ~BinTree();
        @param 
        @return 
    */
    void deletetree(node* n);   //辅助迭代函数
    ~BinTree();

    /**
     *  在二叉排序树中插入元素val，在插入过程中，节点编号从1开始逐渐递增。
        @name insert(int val)
        @param arg1  需要插入的元素值.
        @param arg2  插入元素的父亲节点编号，如果此项值为0，则表示为根结点。
        @param arg3  此元素是左子还是右子。 -1表示左子，1表示右子。
        @return  void
    */
    node* findnode(node* n, int id)const;   //辅助函数
    void insert(int val, int parent, int flg);

    /**
     *  使用前序遍历遍历二叉排序树
        @name p_traversal() const
        @param 
        @return  int*
                 二叉排序树遍历结果,结果需要保存在int数组中。
    */
    void preorder(node* n, std :: vector<int> &res) const;   //辅助迭代函数
    int* p_traversal() const;
    
    /**
     *  使用中序遍历遍历二叉排序树
        @name m_traversal() const
        @param 
        @return  int*
                 二叉排序树遍历结果,结果需要保存在int数组中。
    */
    void inorder(node* n, std :: vector<int> &res) const;   //辅助迭代函数
    int* m_traversal() const;

    /**
     *  使用后序遍历遍历二叉排序树
        @name s_traversal() const
        @param 
        @return  int*
                 二叉排序树遍历结果,结果需要保存在int数组中。
    */
    void postorder(node* n, std :: vector<int> &res) const;     //辅助迭代函数
    int* s_traversal() const;

    /**
     *  获得二叉树节点总数
        @name countNode() const
        @param 
        @return  int 二叉树节点数量
    */
    int countNode() const;

    /**
     *  获得二叉树高度
        @name height() const
        @param 
        @return  int 二叉树高度
    */
    int calculatedepth(node* n)const;   //辅助迭代函数
    int height() const;

    /**
     *  前序化
        @name preThread
        @param prev, cur
        @return
    */    
    void ToPThreadTree(); // 前序线索化辅助函数
    void threadPreorder(node*& prev, node* cur);

    /**
     *  中序化
        @name inThread
        @param prev, cur
        @return
    */ 
    void ToMThreadTree(); // 中序线索化
    void threadPostorder(node*& prev, node* cur);

    /**
     *  后序化
        @name postThread
        @param prev, cur
        @return
    */
    void ToSThreadTree(); // 后序线索化   
    void threadInorder(node*& prev, node* cur);

    int GetLson(const int id); // 获取左孩子节点编号
    int GetRson(const int id); // 获取右孩子节点编号
};

#endif